// 给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

// 例如：

// 输入: 二叉搜索树:
//               5
//             /   \
//            2     13

// 输出: 转换为累加树:
//              18
//             /   \
//           20     13

#include <stack>

using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 从右向左的中序遍历，右中左
class Solution1 {
public:
    TreeNode* convertBST(TreeNode* root) {
        int sum{};
        func(root, sum);
        return root;
    }
    void func(TreeNode*& node, int& sum) {
        if (!node) return;
        func(node->right, sum);
        node->val += sum;
        sum = node->val;
        func(node->left, sum);
    }
};

// 自身递归
class Solution2 {
public:
    TreeNode* convertBST(TreeNode* root) {
        if (!root) return nullptr;
        convertBST(root->right);
        root->val += sum;
        sum = root->val;
        convertBST(root->left);
        return root;
    }
private:
    int sum{};
};

// 中序遍历的迭代写法
class Solution3 {
public:
    TreeNode* convertBST(TreeNode* root) {
        if (!root) return nullptr;
        int sum{};
        stack<TreeNode*> st{};
        TreeNode *p = root;
        while (p || !st.empty()) {
            while (p) {
                st.push(p);
                p = p->right;
            }
            p = st.top();
            st.pop();
            p->val += sum;
            sum = p->val;
            p = p->left;
        }
        return root;
    }
};

/* 反序的中序遍历
*/
class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        if (root == nullptr) {
            return nullptr;
        }
        postOrder(root);
        return root;
    }
    void postOrder(TreeNode* root) {
        if (root == nullptr) {
            return;
        }
        if (root->right) {
            postOrder(root->right);
        }
        root->val += curSum;
        curSum = root->val;
        if (root->left) {
            postOrder(root->left);
        }
    }
private:
    int curSum{0};
};

/* 反序的中序遍历
时间复杂度：O(n)
空间复杂度：O(n)
*/
class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        if (root != nullptr) {
            convertBST(root->right);
            root->val += curSum;
            curSum = root->val;
            convertBST(root->left);
        }
        return root;
    }
private:
    int curSum{0};
};

/* Morris遍历
反序中序遍历
时间复杂度：O(n)
空间复杂度：O(1)
*/
class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        int sum{0};
        TreeNode* node = root;
        while (node) {
            if (node->right == nullptr) {
                // 如果当前节点的右子节点为空，处理当前节点，并遍历当前节点的左子节点
                sum += node->val;
                node->val = sum;
                node = node->left;
            } else {
                // 如果当前节点的右子节点不为空，找到当前节点右子树的最左节点（该节点为当前节点中序遍历的前驱节点）
                TreeNode* succ = getSuccessor(node);
                if (succ->left == nullptr) {
                    // 如果最左节点的左指针为空，将最左节点的左指针指向当前节点，遍历当前节点的右子节点
                    succ->left = node;
                    node = node->right;
                } else {
                    // 如果最左节点的左指针不为空，将最左节点的左指针重新置为空（恢复树的原状），处理当前节点，并将当前节点置为其左节点
                    succ->left = nullptr;
                    sum += node->val;
                    node->val = sum;
                    node = node->left;
                }
            }
        }
        return root;
    }
    // 如果当前节点的右子节点不为空，找到当前节点右子树的最左节点（该节点为当前节点中序遍历的前驱节点）
    TreeNode* getSuccessor(TreeNode* node) {
        TreeNode* succ = node->right;
        while (succ->left != nullptr && succ->left != node) {
            succ = succ->left;
        }
        return succ;
    }
};